home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 46 / Amiga Format CD46 (1999-10-20)(Future Publishing)(GB)[!][issue 1999-12].iso / -in_the_mag- / reader_requests / scilab / man / man-part1 / cat6 / semidef.6 < prev   
Text File  |  1999-09-16  |  4KB  |  133 lines
  1.  
  2.  
  3.  
  4. semidef(1)                     Scilab Function                     semidef(1)
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11. NAME
  12.   semidef - semidefinite programming
  13.  
  14. CALLING SEQUENCE
  15.   [x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options)
  16.  
  17. PARAMETERS
  18.  
  19.   x0        : m x 1 real column vector (must be strictly primal feasible, see
  20.             below)
  21.  
  22.   Z0        : L x 1 real vector (compressed form of a strictly feasible dual
  23.             matrix, see below)
  24.  
  25.   F         : L x (m+1) real matrix
  26.  
  27.   blck_szs  :  p x 2 integer matrix (sizes of the blocks) defining the dimen-
  28.             sions of the (square) diagonal blocks size(Fi(j)=blck_szs(j)
  29.             j=1,...,m+1.
  30.  
  31.   c         : m x 1 real vector
  32.  
  33.   options   : row vector with five entries [nu,abstol,reltol,0,maxiters]
  34.  
  35.   ul        : row vector with two entries
  36.  
  37. DESCRIPTION
  38.   [x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options) solves semidefinite pro-
  39.   gram:
  40.  
  41.       minimize    c'*x
  42.       subject to  F_0 + x_1*F_1 + ... + x_m*F_m  >= 0
  43.  
  44.    and its dual
  45.  
  46.       maximize    -Tr F_0 Z
  47.       subject to  Tr F_i Z = c_i, i=1,...,m
  48.                   Z >= 0
  49.  
  50.   exploiting block structure in the matrices F_i.
  51.  
  52.   It interfaces L. Vandenberghe and S. Boyd sp.c program.
  53.  
  54.   The Fi's matrices are stored columnwise in F in compressed format: if
  55.   F_i^j, i=0,..,m, j=1,...,L denote the jth (symmetric) diagonal block of
  56.   F_i, then
  57.       [ pack(F_0^1)  pack(F_1^1) ...  pack(F_m^1) ]
  58.       [ pack(F_0^2)  pack(F_1^2) ...  pack(F_m^2) ]
  59.   F=  [   ...       ...          ...              ]
  60.       [ pack(F_0^L)  pack(F_1^L) ...  pack(F_m^L) ]
  61.   where pack(M), for symmetric M, is the vector
  62.   [M(1,1);M(1,2);...;M(1,n);M(2,2);M(2,3);...;M(2,n);...;M(n,n)] (obtained by
  63.   scanning columnwise the lower triangular part of M).
  64.  
  65.   blck_szs gives the size of block j, ie, size(F_i^j)=blck_szs(j).
  66.  
  67.   Z is a block diagonal matrix with L blocks Z^0, ..., Z^{L-1}.  Z^j has size
  68.   blck_szs[j] times blck_szs[j].  Every block is stored using packed storage
  69.   of the lower triangular part.
  70.  
  71.   The 2 vector ul contains the primal objective value c'*x and the dual
  72.   objective value -Tr F_0*Z.
  73.  
  74.   The entries of options are respectively: nu = a real parameter which ntrols
  75.   the rate of convergence.  abstol =   absolute tolerance.  reltol =  rela-
  76.   tive tolerance (has a special meaning when negative).  tv  target value,
  77.   only referenced if reltol < 0.  iters =  on entry: maximum number of itera-
  78.   tions >= 0, on exit: the number of iterations taken.
  79.  
  80.   info  returns 1 if maxiters exceeded,  2 if absolute accuracy is reached, 3
  81.   if relative accuracy is reached, 4 if target value is reached, 5 if target
  82.   value is  not achievable;  negative values indicate errors.
  83.  
  84.   Convergence criterion:
  85.    (1) maxiters is exceeded
  86.    (2) duality gap is less than abstol
  87.    (3) primal and dual objective are both positive and
  88.        duality gap is less than (reltol * dual objective)
  89.        or primal and dual objective are both negative and
  90.        duality gap is less than (reltol * minus the primal objective)
  91.    (4) reltol is negative and
  92.        primal objective is less than tv or dual objective is greater
  93.        than tv
  94.  
  95. EXAMPLE
  96.   F0=[2,1,0,0;
  97.       1,2,0,0;
  98.       0,0,3,1
  99.       0,0,1,3];
  100.   F1=[1,2,0,0;
  101.       2,1,0,0;
  102.       0,0,1,3;
  103.       0,0,3,1]
  104.   F2=[2,2,0,0;
  105.       2,2,0,0;
  106.       0,0,3,4;
  107.       0,0,4,4];
  108.   blck_szs=[2,2];
  109.   F01=F0(1:2,1:2);F02=F0(3:4,3:4);
  110.   F11=F1(1:2,1:2);F12=F1(3:4,3:4);
  111.   F21=F2(1:2,1:2);F22=F2(3:4,3:4);
  112.   x0=[0;0]
  113.   Z0=2*F0;
  114.   Z01=Z0(1:2,1:2);Z02=Z0(3:4,3:4);
  115.   FF=[[F01(:);F02(:)],[F11(:);F12(:)],[F21(:);F22(:)]]
  116.   ZZ0=[[Z01(:);Z02(:)]];
  117.   c=[trace(F1*Z0);trace(F2*Z0)];
  118.   options=[10,1.d-10,1.d-10,0,50];
  119.   [x,Z,ul,info]=semidef(x0,pack(ZZ0),pack(FF),blck_szs,c,options)
  120.   w=vec2list(unpack(Z,blck_szs),[blck_szs;blck_szs]);Z=sysdiag(w(1),w(2))
  121.   c'*x+trace(F0*Z)
  122.   spec(F0+F1*x(1)+F2*x(2))
  123.   trace(F1*Z)-c(1)
  124.   trace(F2*Z)-c(2)
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.